/*
#Copyright (c) 2013, Philippe Bordron <philippe.bordron@gmail.com>
#
# This file is part of SIPPER.
#
# DCC is free software: you can redistribute it and/or modify
# it under the terms of the GNU LESSER GENERAL PUBLIC LICENSE as published by
# the Free Software Foundation, either version 3 of the License, or
# (at your option) any later version.
#
# DCC is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
# GNU LESSER GENERAL PUBLIC LICENSE for more details.
#
# You should have received a copy of the GNU LESSER GENERAL PUBLIC LICENSE
# along with SIPPER.  If not, see <http://www.gnu.org/licenses/>
*/
package combi.wip.graph.algo;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

import org.jgrapht.DirectedGraph;
import org.jgrapht.GraphPath;
import org.jgrapht.graph.DefaultDirectedWeightedGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.GraphPathImpl;

import combi.sipper.io.IOSimpleGraph;
import combi.wip.graph.algo.utils.heaps.BinaryHeap;
import combi.wip.graph.algo.utils.heaps.Heap;

public class DijsktraShortestPath<V,E extends DefaultWeightedEdge> {

	DirectedGraph<V, E> graph;
	V start, end;
	Map<V, Double> distance;
	Heap<V, Double> heap;
	Map<V, E> pred;


	public DijsktraShortestPath (DirectedGraph<V, E> graph, V start, V end)
	{
		this.graph = graph;
		this.start = start;
		this.end = end;
		this.distance = new HashMap<V,Double>();
		this.pred = new HashMap<V, E>();
		for (V v : graph.vertexSet())
		{
			distance.put(v, Double.POSITIVE_INFINITY);
		}
		distance.put(start, 0.0);
		heap = new BinaryHeap<V,Double>(Double.POSITIVE_INFINITY);
	}

	private void run()
	{
		heap.insert(start, distance.get(start));
		V v;
		do {
			v = heap.removeMin();
			//System.err.println("Heap remove : " + v);
			for(E e : graph.outgoingEdgesOf(v))
			{
				//System.err.println("Outgoing : " + e);
				relax(v, e);
			}
		}
		while (!v.equals(end) && !heap.isEmpty());
		heap.clear();
	}

	public GraphPath<V,E> getPath()
	{
		List<E> result = new ArrayList<E>(); 
		if (distance.get(end) != Double.POSITIVE_INFINITY)
		{
			V temp = end;
			V p = null;
			E e = null;
			do
			{
				e = this.pred.get(temp);
				p = this.graph.getEdgeSource(e);
				result.add(e);
				temp = p;
			}
			while(!p.equals(start));
			Collections.reverse(result);
		}
		return new GraphPathImpl<V, E>(graph, start, end, result, distance.get(end));
	}

	public Double getPathLength()
	{
		return distance.get(end);
	}

	private void relax(V v1, E edge)
	{
		//V v1 = graph.getEdgeSource(edge);
		V v2 = graph.getEdgeTarget(edge);
		Double weight = graph.getEdgeWeight(edge);
		//System.err.println(distance.get(v2) +  ">" + distance.get(v1) + "+" +weight +"=" +(distance.get(v1) + weight));
		if (distance.get(v2) > distance.get(v1) + weight)
		{
			//System.err.println("Relax : " + v1+ ":" + v2);
			//System.err.println(heap);
			distance.put(v2, distance.get(v1) + weight);
			if (pred.containsKey(v2))
			{
				//System.err.println("Heap decrease : " + v2 +"->" + distance.get(v2));
				heap.decreaseKey(v2, distance.get(v2));
			}
			else{	
				//System.err.println("Heap insert : " + v2 + "->" + distance.get(v2));
				heap.insert(v2, distance.get(v2));
			}
			pred.put(v2,edge);
			//System.err.println(heap);
		}
	}
	
	public static void main(String[] argv) throws IOException
	{
		DefaultDirectedWeightedGraph<Integer, DefaultWeightedEdge> graph = IOSimpleGraph.load(argv[0]);
		//System.out.println(graph);
		long oldtime;
		long newtime;


		/*-----------------------------*/
		oldtime = System.currentTimeMillis();
		DijsktraShortestPath<Integer,DefaultWeightedEdge> mydijkstra = new DijsktraShortestPath<Integer,DefaultWeightedEdge>(graph, Integer.valueOf(argv[1]),Integer.valueOf(argv[2]));
		mydijkstra.run();
		GraphPath<Integer,DefaultWeightedEdge> mypath = mydijkstra.getPath();
		newtime = System.currentTimeMillis();
		System.out.println(mydijkstra.getPathLength()+":"+mypath);
		System.out.println("in "+ (newtime - oldtime) + "ms");
		

		/*-----------------------------*/
		oldtime = System.currentTimeMillis();
		org.jgrapht.alg.DijkstraShortestPath<Integer,DefaultWeightedEdge> dijkstra = new org.jgrapht.alg.DijkstraShortestPath<Integer,DefaultWeightedEdge>(graph, Integer.valueOf(argv[1]), Integer.valueOf(argv[2]));
		GraphPath<Integer,DefaultWeightedEdge> path = dijkstra.getPath();
		newtime = System.currentTimeMillis();
		System.out.println(dijkstra.getPathLength()+":"+path);
		System.out.println("in "+ (newtime - oldtime) + "ms");
		
	}
	
	
}
